約 4,481,230 件
https://w.atwiki.jp/tmiya/pages/87.html
17.7 非同期チャネル プロセス内通信の基本的な方法には非同期チャネルがあります。その実装では次の単純な連結リストを利用しています。 class LinkedList[A] { var elem A = _ var next LinkedList[A] = null } 連結リストへの要素の挿入・追加を助けるために、連結リストの中への参照はすべて、リストの先頭を概念的に表すノードの手前のノードを指します。空きの連結リストはダミーノードで始まり、次の要素は nullです。 チャネルクラスは、送られたがまだ読み出されていないデータを保持するのに連結リストを使います。反対の端では、空きのチャネルから読み出そうとするスレッドは nreaders フィールドをインクリメントすることで自分を登録し、通知されるのを待ちます。 package scala.concurrent class Channel[A] { class LinkedList[A] { var elem A = _ var next LinkedList[A] = null } private var written = new LinkedList[A] private var lastWritten = written private var nreaders = 0 def write(x A) = synchronized { lastWritten.elem = x lastWritten.next = new LinkedList[A] lastWritten = lastWritten.next if (nreaders 0) notify() } def read A = synchronized { if (written.next == null) { nreaders = nreaders + 1; wait(); nreaders = nreaders - 1 } val x = written.elem written = written.next x } } 前ページ 17 章 目次 次ページ 名前 コメント
https://w.atwiki.jp/tmiya/pages/86.html
17.6 リーダー/ライター より複雑な同期の形態では、共通リソースを変更することなくアクセスする リーダー と、アクセスと変更の両方が可能な ライター を区別します。リーダーとライターを同期させるために startRead、startWrite、endRead、endWrite、その他を実装する必要があります。 多数の並行リーダーがある 同時にはただ１つのライターのみ可能 ペンディング中の書き込み要求は、ペンディング中の読み込み要求よりも優先するが、実行中のリード操作をプリエンプトしない 次のリーダー/ライター ロックの実装は メールボックス に基づいています (17.10節参照)。 import scala.concurrent._ class ReadersWriters { val m = new MailBox private case class Writers(n Int), Readers(n Int) { m send this } Writers(0); Readers(0) def startRead = m receive { case Writers(n) if n == 0 = m receive { case Readers(n) = Writers(0); Readers(n+1) } } def startWrite = m receive { case Writers(n) = Writers(n+1) m receive { case Readers(n) if n == 0 = } } def endRead = m receive { case Readers(n) = Readers(n-1) } def endWrite = m receive { case Writers(n) = Writers(n-1); if (n == 0) Readers(0) } } 前ページ 17 章 目次 次ページ 名前 コメント
https://w.atwiki.jp/tmiya/pages/81.html
17.2 同期変数 同期化された変数(あるいは縮めて、同期変数)は変数の読み出しと設定用に、get と put 操作を提供します。get 操作は、変数が定義されるまでブロックします。unset 操作は、変数を未定義状態にリセットします。 次は同期変数の標準的な実装です。 package scala.concurrent class SyncVar[A] { private var isDefined Boolean = false private var value A = _ def get = synchronized { while (!isDefined) wait() value } def set(x A) = synchronized { value = x; isDefined = true; notifyAll() } def isSet Boolean = synchronized { isDefined } def unset = synchronized { isDefined = false } } 前ページ 17 章 目次 次ページ 名前 コメント
https://w.atwiki.jp/tmiya/pages/65.html
10.5 For の一般化 (Generalizing For) for 内包表記の翻訳が、メソッド map、flatMap、filter の存在だけに依存していることを見てきました。したがって、リスト以外のオブジェクトを生成するジェネレータについても、同じ記法を適用できます。それらのオブジェクトは３つのキーとなる関数 map、flatMap、filter だけをサポートすればよいのです。 標準 Scala ライブラリには、それら３つのメソッドと for 内包表記をサポートする抽象化が他にもいくつかあります。それらのいくつかは後の章で目にするでしょう。プログラマは自分が定義する型について for 内包表記を使えるようにするために、この原則を利用できます。そのような型は、単にメソッド map、flatMap、filter だけが必要なのです。 このことが役に立つ例はいくつもあります。たとえばデータベース・インタフェース、XML 木、オプション値などです。 一つ注意すべき点を。for 内包表記の翻訳結果に型整合性があることは、自動的には保証されません。これを保証するためには、map、flatMap、filter の型が、クラス List 中のそれらメソッドの型と本質的に似ていることが必要です。 より正確に言えば、for 内包表記を可能にしたい、パラメータ化されたクラス C[A] があるとしましょう。すると C は次のような型を持った map、flatMap、filter を定義しなくてはなりません。 def map[B](f A = B) C[B] def flatMap[B](f A = C[B]) C[B] def filter(p A = Boolean) C[A] これらの型を Scala コンパイラの中で静的に強制することは、よい考えに思えます。たとえば for 内包表記をサポートするすべての型が、これらのメソッドを持つ標準トレイトを実装するよう要求するとかです(*1)。問題は、そのような標準的なトレイトはクラス C の同一性に対して抽象化、たとえば C を型パラメータとしてとるとか、をしなくてはならないことです。このパラメータは型コンストラクタであり、map や flatMap メソッドのシグネチャにおいて 複数の異なる 型に適用される、ということに注意すべきです。不運にも Scala の型システムはこのコンストラクトを表現するには弱過ぎます。なぜなら完全に適用される型である、型パラメータしか扱えないからです。 (*1) プログラミング言語 Haskell には同様のコンストラクトがあり、この抽象化は "monad with zero" と呼ばれています。 前ページ 10 章 目次 次ページ 名前 コメント
https://w.atwiki.jp/tmiya/pages/42.html
第 6 章 クラスとオブジェクト Scala には組み込みの有理数型はありませんが、クラスを使って簡単に定義できます。次が実装例です。 class Rational(n Int, d Int) { private def gcd(x Int, y Int) Int = { if (x == 0) y else if (x 0) gcd(-x, y) else if (y 0) -gcd(x, -y) else gcd(y % x, x) } private val g = gcd(n, d) val numer Int = n/g val denom Int = d/g def +(that Rational) = new Rational(numer * that.denom + that.numer * denom, denom * that.denom) def -(that Rational) = new Rational(numer * that.denom - that.numer * denom, denom * that.denom) def *(that Rational) = new Rational(numer * that.numer, denom * that.denom) def /(that Rational) = new Rational(numer * that.denom, denom * that.numer) } 有理数を、分子 n と分母 d の２つのコンストラクタ引数をとるクラスとして定義しています。このクラスは有理数上の演算メソッドだけではなく、分子と分母を返すフィールドも提供します。各演算メソッドは操作の右オペランドをパラメータにとります。操作の左オペランドは、常にそのメソッドがメンバであるような有理数です。 プライベート・メンバ 有理数の実装では、２つの整数の最大公約数を計算するプライベートなメソッド gcd を定義し、また、コンストラクタ引数の gcd を格納するプライベートなフィールド g も定義します。これらのメンバはクラス Rational の外からはアクセスできません。それらはクラスの実装において、コンストラクタ引数を公約数で割って、分子と分母を常に正規形(約分された形)にするために使います。 オブジェクト生成とアクセス 有理数の使い方の例として、i の範囲が 1 から 10 まで時に、1/i の和を印刷するプログラムを示します。 var i = 1 var x = new Rational(0, 1) while (i = 10) { x += new Rational(1, i) i += 1 } println("" + x.numer + "/" + x.denom) + は左オペランドに文字列を、右オペランドに任意の型の値をとります。右オペランドを文字列に変換し、それを左オペランドに追加した結果を返します。 継承とオーバーライド Scala のすべてのクラスは親クラスを持ち、それを継承しています。クラス定義の中で親クラスが指定されていない場合、ルート型 scala.AnyRef が暗黙のうちに仮定されます (Java の実装でいうと、この型は java.lang.Object のエイリアスです)。 たとえばクラス Rational を次のように定義しても同じことです。 class Rational(n Int, d Int) extends AnyRef { ... // as before } クラスは親クラスのメンバをすべて継承します。継承したメンバを再定義 (つまり、 オーバーライド ) できます。たとえばクラス java.lang.Object は、オブジェクトの文字列表現を返すメソッド toString を定義しています。 class Object { ... def toString String = ... } Object での toString は、オブジェクトのクラス名と数からなる文字列として実装されています。このメソッドを有理数のオブジェクト用に再定義すると役に立ちます。 class Rational(n Int, d Int) extends AnyRef { ... // as before override def toString = "" + numer + "/" + denom } 注意すべき点は、Java とは異なり、定義の再定義では手前に override 修飾子が必要なことです。 もしクラス A がクラス B を継承しているなら、型 A のオブジェクトは、型 B のオブジェクトが期待される所ではどこでも使用できます。このような場合、型 A は型 B に 適合する (conform)、といいます。たとえば Rational は AnyRef に適合します。したがって Rational 値を AnyRef 型の変数に代入できます。 var x AnyRef = new Rational(1, 2) パラメータなしのメソッド Java とは異なり、Scala のメソッドはパラメータリストを必ずしも必要としません。次の square メソッドがその例です。このメソッドは単に名前を書くだけで呼び出されます。 class Rational(n Int, d Int) extends AnyRef { ... // as before def square = new Rational(numer*numer, denom*denom) } val r = new Rational(3, 4) println(r.square) // prints 9/16 * これは、パラメータなしメソッドは numer のような値フィールドと同じようにアクセスされるということです。値とパラメータなしメソッドの違いはそれらの定義にあります。値の右辺はオブジェクトが作成された時に評価され、以後は値が変化しません。その一方で、パラメータなしメソッドの右辺はメソッドが呼ばれる度に評価されます。フィールドとパラメータなしメソッドのアクセス方法が統一されているのでクラス実装者の自由度が増します。しばしば、あるバージョンではフィールドだったものが次のバージョンでは計算された値だったりします。統一的なアクセスのおかげで、クライアントは変更による書き直しが不要になります。 抽象クラス 整数の集合に対して、２つの操作 incl と contains を持つクラスを書く課題について考えてみましょう。(s incl x) は集合 s の要素すべてと、要素 x を持つ新しい集合を返すべきです。(s contains x) は、集合 s が要素 x を含む時は true を、さもなければ false を返すべきです。そのような集合のインターフェイスは次のようになります。 abstract class IntSet { def incl(x Int) IntSet def contains(x Int) Boolean } IntSet は 抽象クラス と分類されます。これは２つの結果をもたらします。一つは、抽象クラスは 延期された メンバを持ち、それらは宣言はあっても実装はありません。この場合、incl と contains の両方がそのようなメンバです。二つ目は、抽象クラスには未実装のメンバがあるかもしれないので、そのクラスのオブジェクトを new で生成できません。その一方で、抽象クラスは他のクラスの基底クラスとして使うことができ、継承したクラスでは延期されたメンバを実装します。 トレイト Scala では、abstract class の代わりにキーワード trait をよく使います。トレイトは、他のクラスに付け加えるための抽象クラスです。これはトレイトが未知の親クラスにメソッドやフィールドをいくつか追加するからです。たとえば、トレイト Bordered は様々なグラフィカルコンポーネントに縁を追加するのに使われるでしょう。別の使い方としては、様々なクラスによって提供される機能のシグネチャをトレイトが集約する、という Java のインターフェイスがするようなやり方です。 IntSet はこの分類に入るので、トレイトとしても定義できます。 trait IntSet { def incl(x Int) IntSet def contains(x Int) Boolean } 抽象クラスの実装 たとえば集合を二分木で実装することにしましょう。木の形には２つの可能性があります。空集合を表す木と、整数１つと２つの部分木からなる木です。次がその実装です。 class EmptySet extends IntSet { def contains(x Int) Boolean = false def incl(x Int) IntSet = new NonEmptySet(x, new EmptySet, new EmptySet) } class NonEmptySet(elem Int, left IntSet, right IntSet) extends IntSet { def contains(x Int) Boolean = if (x elem) left contains x else if (x elem) right contains x else true def incl(x Int) IntSet = if (x elem) new NonEmptySet(elem, left incl x, right) else if (x elem) new NonEmptySet(elem, left, right incl x) else this } EmptySet と NonEmptySet の両方とも IntSet を継承します。これは、型 EmptySet と NonEmptySet が型 IntSet に適合すること --- 型 EmptySet や NonEmptySet の値は、型 IntSet の値が必要なところではどこでも使えることを意味します。 演習 6.0.1 メソッド union と intersection を２つの集合の結びと交わりとなるように書きなさい。 演習 6.0.2 要素 x を取り除いた集合を返すメソッド def excl(x Int) を追加しなさい。そうするために便利なテスト用メソッド def isEmpty Boolean も、集合に対して実装しなさい。 動的束縛 (Scala を含む) オブジェクト指向言語はメソッド呼び出しのときに 動的ディスパッチ を用います。これは、メソッド呼び出しで起動されるコードは、メソッドを含むオブジェクトの実行時型に依存するということです。たとえば式 s contains 7、ただし s は宣言された型 s IntSet の値だとします。もしそれが EmptySet の値なら、実行されるのはクラス EmptySet の contains の実装であり、NonEmptySet の値の場合も同様です。この振る舞いは評価の置き換えモデルの直接的な帰結です。たとえば (new EmptySet).contains(7) - (クラス EmptySet の contains 本体で置き換えることで) false あるいは new NonEmptySet(7, new EmptySet, new EmptySet).contains(1) - (クラス NonEmptySet の contains 本体で置き換えることで) if (1 7) new EmptySet contains 1 else if (1 7) new EmptySet contains 1 else true - (条件式を書き換えて) new EmptySet contains 1 - (クラス EmptySet の contains 本体で置き換えることで) false . 動的メソッドディスパッチは高階関数呼び出しと似ています。どちらの場合にも、実行されるコードの正体は実行時にしか分かりません。この類似性は表面上のものにとどまりません。実際、Scala はすべての関数値をオブジェクトとして表現しています (8.6 節参照)。 オブジェクト 整数集合の以前の実装では、空集合は new EmptySet で表現されていました。つまり空集合値が必要になる度に、毎回新しいオブジェクトが生成されました。値 empty を一度だけ定義して、その値をすべての new EmptySet の出現の代わりに使えば、不必要なオブジェクト生成を避けることができます。たとえば val EmptySetVal = new EmptySet この方法の問題の一つは、このような値定義は Scala の正しいトップレベルでの定義ではない、ということです。これは別のクラスかオブジェクトの一部でなくてはなりません。またクラス EmptySet の定義は少しばかりやり過ぎています。もしたった一つのオブジェクトにだけ関心があるなら、なぜオブジェクト用のクラスを定義するのでしょう？ より直接的な方法は オブジェクト定義 を使うことです。代わりの、より洗練された空集合の定義は次のようになります。 object EmptySet extends IntSet { def contains(x Int) Boolean = false def incl(x Int) IntSet = new NonEmptySet(x, EmptySet, EmptySet) } オブジェクト定義の構文はクラス定義の構文に従います。オプションの extends 節とオプションの本体があります。クラスの場合のように、extends 節はオブジェクトが継承するメンバを定義し、一方で本体はオーバーライドするあるいは新規のメンバを定義します。しかしオブジェクト定義はただ１つのオブジェクトだけを定義するため、同じ構造を持った他のオブジェクトを new で生成できません。したがってオブジェクト定義には、クラス定義にはあるかもしれないコンストラクタパラメータはありません。 オブジェクト定義は Scala プログラムのどこにでも、トップレベルにも、書けます。Scala ではトップレベルのエンティティの実行順序は固定されていないため、オブジェクト定義によって定義されたオブジェクトがいつ生成され初期化されるのか、正確に知りたい人もいるでしょう。その答えは、オブジェクトはそのメンバが最初にアクセスされる時に生成される、というものです。この戦略は 遅延評価 と呼ばれています。 標準クラス Scala は純粋なオブジェクト指向言語です。これは Scala のすべての値がオブジェクトである、ということです。実際 int や boolean のようなプリミティブ型でさえ特別扱いされません。それらはモジュール Predef において、Scala クラスの型エイリアスとして定義されています。 type boolean = scala.Boolean type int = scala.Int type long = scala.Long ... コンパイラは効率化のために通常、scala.Int 型の値を 32 bit 整数で、scala.Boolean 型の値を Java の boolean で、等と表現します。しかし必要に応じてこれらの特別な表現をオブジェクトに変換します。たとえばプリミティブの Int 値が AnyRef 型のパラメータをとる関数に渡される時です。したがってプリミティブ値の特別な表現は単に最適化のためであり、プログラムの意味を変えません。 次がクラス Boolean の仕様です。 package scala abstract class Boolean { def (x = Boolean) Boolean def || (x = Boolean) Boolean def ! Boolean def == (x Boolean) Boolean def != (x Boolean) Boolean def (x Boolean) Boolean def (x Boolean) Boolean def = (x Boolean) Boolean def = (x Boolean) Boolean } Boolean はクラスとオブジェクトだけを使って定義でき、組み込みのブール値や数値の型を参照する必要はありません。Boolean 型の一つの実装を次に示します。これは標準 Scala ライブラリの実際の実装ではありません。効率化のために標準の実装では、組み込みのブール値を使います。 package scala abstract class Boolean { def ifThenElse(thenpart = Boolean, elsepart = Boolean) def (x = Boolean) Boolean = ifThenElse(x, false) def || (x = Boolean) Boolean = ifThenElse(true, x) def ! Boolean = ifThenElse(false, true) def == (x Boolean) Boolean = ifThenElse(x, x.!) def != (x Boolean) Boolean = ifThenElse(x.!, x) def (x Boolean) Boolean = ifThenElse(false, x) def (x Boolean) Boolean = ifThenElse(x.!, false) def = (x Boolean) Boolean = ifThenElse(x, true) def = (x Boolean) Boolean = ifThenElse(true, x.!) } case object True extends Boolean { def ifThenElse(t = Boolean, e = Boolean) = t } case object False extends Boolean { def ifThenElse(t = Boolean, e = Boolean) = e } 次はクラス Int の仕様の一部です。 package scala abstract class Int extends AnyVal { def toLong Long def toFloat Float def toDouble Double def + (that Double) Double def + (that Float) Float def + (that Long) Long def + (that Int) Int // analogous for -, *, /, % def (cnt Int) Int // analogous for , def (that Long) Long def (that Int) Int // analogous for |, ^ def == (that Double) Boolean def == (that Float) Boolean def == (that Long) Boolean // analogous for !=, , , =, = } クラス Int も原理的にはオブジェクトとクラスだけで、組み込みの整数型を参照することなく実装できます。その方法を知るために、少しだけ簡単な問題、自然数を表す型 Nat の実装方法を考えみましょう。次は抽象クラス Nat の定義です。 abstract class Nat { def isZero Boolean def predecessor Nat def successor Nat def + (that Nat) Nat def - (that Nat) Nat } クラス Nat の操作を実装するために、子オブジェクト Zero と子クラス Succ (次の数) を定義します。それぞれの数 N は、Zero に Succ コンストラクタを N 回適用したものです。 new Succ( ... new Succ(Zero) ... ) ------- N 回 ------- オブジェクト Zero の定義はそのままです。 object Zero extends Nat { def isZero Boolean = true def predecessor Nat = error("negative number") def successor Nat = new Succ(Zero) def + (that Nat) Nat = that def - (that Nat) Nat = if (that.isZero) Zero else error("negative number") } Zero における、前の数(predecessor)および減算(-)関数の実装は、Error 例外を送出し、与えられたエラーメッセージと共にプログラムをアボートします。 次は「次の数」クラスの実装です。 class Succ(x Nat) extends Nat { def isZero Boolean = false def predecessor Nat = x def successor Nat = new Succ(this) def + (that Nat) Nat = x + that.successor def - (that Nat) Nat = x - that.predecessor } メソッド successor の実装に注意して下さい。ある数の次の数を作るために、Succ コンストラクタにオブジェクト自身を引数として渡す必要があります。オブジェクト自身は予約語 this で参照できます。 + と - の実装はそれぞれ、コンストラクタ引数を受け手とする再帰呼び出しを含みます。再帰は、受け手が Zero オブジェクトの時 (そのように数を構成したので、それが起きることは保証されています) に終わります。 演習 6.0.3 整数の実装 Integer を書きなさい。実装はクラス Nat の操作すべてをサポートし、加えて、次の２つのメソッドもサポートしなさい。 def isPositive Boolean def negate Integer 最初のメソッドは数が正であれば true を返すものとします。二つ目のメソッドは数の符号を変えます。実装の中で Scala の標準の数値クラスを使ってはいけません (ヒント Integer の実装方法は二つ可能です。一つは既存の Nat 実装を利用し、整数を自然数と符号で表すものです。あるいは３つの子クラスとして Zero を 0 に、Succ を正の数のため、Pred を負の数のために使い、既知の Nat 実装を Integer へ一般化できます)。 この章で紹介した構文 型 (Types) Type = ... | ident 型は、クラスを表す任意の識別子です。 式 (Expressions) Expr = ... | Expr . ident | new Expr | this 式は、オブジェクト生成、オブジェクト値を持つ式 E のメンバ m を選択する E.m、あるいは予約語の this です。 定義と宣言 (Definitions and Declarations) Def = FunDef | ValDef | ClassDef | TraitDef | ObjectDef ClassDef = [ abstract ] class ident [ ( [Parameters] ) ] [ extends Expr] [ { {TemplateDef} } ] TraitDef = trait ident [ extends Expr] [ { {TemplateDef} } ] ObjectDef = object ident [ extends Expr] [ { {ObjectDef} } ] TemplateDef = [Modifier] (Def | Dcl) ObjectDef = [Modifier] Def Modifier = private | override Dcl = FunDcl | ValDcl FunDcl = def ident { ( [Parameters] ) } Type ValDcl = val ident Type 定義は次のようなクラス、トレイト、あるいはオブジェクト定義です。 class C(params) extends B { defs } trait T extends B { defs } object O extends B { defs } クラス、トレイト、オブジェクト定義内の定義 def の手前に、修飾子 private あるいは override を置けます。 抽象クラスとトレイトに宣言を含めることもできます。それらは 延期された 関数や値を型とともに導入しますが、実装は与えません。延期されたメンバは、抽象クラスやトレイトのオブジェクトを生成する前に、サブクラスで実装しておく必要があります。 前ページ 6 章 目次 次ページ お疲れさまです。「新規のmンバ」は「新規のメンバ」のtypoかと・・・ -- ryugate (2008-05-23 00 18 04) ↑を反映。訳で抜けている文章を追加。行頭の+は~+にしないといけないらしい・・・ -- asaq (2008-10-05 13 46 14) 名前 コメント
https://w.atwiki.jp/tmiya/pages/63.html
10.3 For 内包表記の変換 すべての for 内包表記は３つの高階関数 map, flatMap, filter で表現できます。これが翻訳のスキーム(枠組み)であり、Scala コンパイラも使っています。 • 単純な for 内包表記 for (x - e) yield e これは次のように翻訳されます。 e.map(x = e ) • for 内包表記 for (x - e if f; s) yield e ただし f はフィルタで、s は (空でも良い) ジェネレータあるいはフィルタの列。これは次のように翻訳されます。 for (x - e.filter(x = f); s) yield e そして後者の式に対して翻訳が続きます。 • for 内包表記 for (x - e; y - e ; s) yield e ただし s は (空でも良い) ジェネレータあるいはフィルタの列。これは次のように翻訳されます。 e.flatMap(x = for (y - e ; s) yield e ) そして後者の式に対して翻訳が続きます。 たとえば、「和が素数になる整数の組」を例にとると、 for { i - range(1, n) j - range(1, i) if isPrime(i+j) } yield {i, j} この式を翻訳すると次が得られます。 range(1, n) .flatMap(i = range(1, i) .filter(j = isPrime(i+j)) .map(j = (i, j))) 逆に、関数 map, flatMap, filter を for 内包表記で表すこともできます。３つの関数を今度は for 内包表記を使って実装してみます。 object Demo { def map[A, B](xs List[A], f A = B) List[B] = for (x - xs) yield f(x) def flatMap[A, B](xs List[A], f A = List[B]) List[B] = for (x - xs; y - f(x)) yield y def filter[A](xs List[A], p A = Boolean) List[A] = for (x - xs if p(x)) yield x } 驚くことではありませんが、Demo.map の本体の for 内包表記の翻訳は、クラス List の map を呼び出します。同様に、Demo.flatMap と Demo.filter は、クラス List の flatMap と filterの呼び出しへ翻訳されます。 演習 10.3.1 次の関数を for を用いて定義しなさい。 def flatten[A](xss List[List[A]]) List[A] = (xss \ (Nil List[A])) ((xs, ys) = xs ys) 演習 10.3.2 次を高階関数を用いて翻訳しなさい。 for (b - books; a - b.authors if a startsWith "Bird") yield b.title for (b - books if (b.title indexOf "Program") = 0) yield b.title 前ページ 10 章 目次 次ページ 名前 コメント
https://w.atwiki.jp/tmiya/pages/40.html
5.4 まとめ 前の章で、関数は抽象化に必須である、なぜなら計算の一般的な方法を明示できるから、ということ、関数は我々のプログラミング言語において名前の付いた要素であることを見てきました。この章では、それら抽象化は高階関数と組み合わせることで、さらに抽象化できることを示しました。プログラマは抽象化と再利用の機会を探すべきです。最大限に抽象化することが必ずしも最適とは限りませんが、適切な場面で抽象化できるように、抽象化の技法を知ることは重要です。 前ページ 5 章 目次 次ページ
https://w.atwiki.jp/tmiya/pages/61.html
10.1 N クィーン問題 (The N-Queens Problem) for 内包表記は組み合わせパズルを解くのに特に役立ちます。そのようなパズルの一つの例が８クイーン問題 標準的なチェス盤に、８個のクイーンをお互いにチェックしない (クイーンは他の駒が同じ行、列、斜めにある時にチェックできます) ように置け、です。この問題の解法を考えますが、一般化してチェス盤を任意の大きさにします。したがって問題は、n個のクイーンを n x n の大きさのチェス盤に置け、となります。 問題を解くには、クイーンは各行に置かなくてはならないことに注意しましょう。ですから、クイーンを各行に置き、その度に新しく置いたクイーンが、すでに置かれた他のクイーンからチェックされないことを確認します。探索の過程において、行 k のどの場所にクイーンを置いても、それが行 1 から行 k-1 までのどれかのクイーンによってチェックされるかもしれません。そのような場合にはその部分の探索を止め、列 1 から列 k-1 のクイーンの異なる配置で探索を続けます。 以上から、再帰的なアルゴリズムが示唆されます。サイズ n x n の盤に k-1 個のクイーンを置いた解がすでにあるとしましょう。そのような解は、長さ k-1 の列番号のリスト (1 から n の範囲の値) として表現できます。この部分解リストをスタックのように扱います。リストの最初は k-1 行のクイーンの列番号、二番目は k-2 行のクイーンの列番号です。スタックの底は、盤の最初の行のクイーンの列番号です。すべての解はリストのリストとして表現され、各要素が個々の解です。 さて、k 番目のクイーンを置くために、前の解にクイーンを一つ追加し、可能なすべての拡張を作ります。これは長さ k の次の解のリストとなります。このプロセスをチェス盤のサイズ n に達するまで繰り返します。このアルゴリズムは次の関数 placeQueens に表されます。 def queens(n Int) List[List[Int]] = { def placeQueens(k Int) List[List[Int]] = if (k == 0) List(List()) else for { queens - placeQueens(k - 1) column - List.range(1, n + 1) if isSafe(column, queens, 1) } yield column queens placeQueens(n) } 演習 10.1.1 次の関数を書きなさい。 def isSafe(col Int, queens List[Int], delta Int) Boolean この関数は与えられた列 col に置くクイーンが、すでに置かれているクイーンに対して安全か否かを判定します。ここで delta は、クイーンを置く行と、リスト中の最初のクイーンの行との差です。 前ページ 10 章 目次 次ページ 名前 コメント
https://w.atwiki.jp/tmiya/pages/35.html
4.6 末尾再帰 与えられた２つの数の最大公約数を計算する、次の関数について考えてみましょう。 def gcd(a Int, b Int) Int = if (b == 0) a else gcd(b, a % b) 関数評価の置き換えモデルを用いると、gcd(14, 21) は次のように評価されます。 gcd(14, 21) → if (21 == 0) 14 else gcd(21, 14 % 21) → if (false) 14 else gcd(21, 14 % 21) → gcd(21, 14 % 21) → gcd(21, 14) → if (14 == 0) 21 else gcd(14, 21 % 14) → → gcd(14, 21 % 14) → gcd(14, 7) → if (7 == 0) 14 else gcd(7, 14 % 7) → → gcd(7, 14 % 7) → gcd(7, 0) → if (0 == 0) 7 else gcd(0, 7 % 0) → → 7 もう一つの再帰関数 factorial の評価と比較して下さい。 def factorial(n Int) Int = if (n == 0) 1 else n * factorial(n - 1) factorial(5) の適用は次のように書き換えます。 factorial(5) → if (5 == 0) 1 else 5 * factorial(5 - 1) → 5 * factorial(5 - 1) → 5 * factorial(4) → . . . → 5 * (4 * factorial(3)) → . . . → 5 * (4 * (3 * factorial(2))) → . . . → 5 * (4 * (3 * (2 * factorial(1)))) → . . . → 5 * (4 * (3 * (2 * (1 * factorial(0)))) → . . . → 5 * (4 * (3 * (2 * (1 * 1)))) → . . . → 120 ２つの書き換え列には重要な違いがあります。gcd の書き換え列の項は、同じ形を繰り返しています。評価が進んでもその大きさは一定に抑えられています。対照的に factorial の評価では、オペランドの列はどんどん長くなり、評価列の最後でそれらは掛け合わされます。 Scala の実際の実装が項書き換えで行われていないとしても、やはり、書き換え列と同様の空間的な振る舞いをします。gcd の実装をみると、gcd の再帰呼び出しは評価本体の最後のアクションであることに気付きます。gcd は「末尾再帰的」だとも呼ばれます。末尾再帰関数の最後の呼び出しは、関数の先頭への戻りジャンプとして実装できます。その呼び出しの引数は、gcd の現在のインスタンスのパラメータを上書きできるので、新しいスタック空間を必要としません。ですから末尾再帰関数は繰り返し処理であり、一定の空間で実行できます。 対照的に factorial の再帰呼び出しでは、掛け算があとで施されます。ですから新しいスタックフレームが factorial の再帰インスタンス用に割り当てられ、インスタンス終了後に割り当てが除かれます。この階乗関数の設計は末尾再帰的ではありません。実行するには入力パラメータに比例した空間が必要となります。 より一般的には、もし関数の最後のアクションが他の (同じでも可) 関数の呼び出しであれば、両方の関数は一つのスタックフレームだけで充分です。そのような呼び出しは「末尾呼び出し(tail call)」と呼ばれます。原理的には、末尾呼び出しは常に呼び出した関数のスタックフレームを再利用できます。しかし (Java VM のような) いくつかの実行時環境では、末尾呼び出しでのスタックフレーム再利用を効率化するプリミティブに欠けています。ですから製品品質の Scala の実装では、直接的な末尾再帰(最後のアクションが自分自身の呼び出しとなる再帰)のスタックフレーム再利用だけが要求されています。他の末尾呼び出しも最適化されるかもしれませんが、多くの実装でそうなるということは、当てにすべきではありません。 演習 4.6.1 factorial の末尾再帰版をデザインしなさい。 前ページ 4 章 目次 次ページ お疲れさまです。「評価が進んでもその大きさは定数で・・・」の「定数で」は「一定に」の方が適しているように思います。 -- ryugate (2008-05-19 22 13 10) あちこちのご指摘どうもありがとうございます＞ryugateさん。現時点ではとりあえず誤字誤訳も含めてまずは一巡翻訳しようと考えております。その間に皆さんに色々ご指摘頂き、纏めて修正していこうかと。訳語などもどこまで日本語にするかあるいはカタカナにするかなど迷っている箇所が多いので、気軽にアドバイス頂ければと思います。 -- tmiya (2008-05-23 07 06 24) 名前 コメント
https://w.atwiki.jp/tmiya/pages/85.html
17.5 セマフォ プロセス同期の一般的なメカニズムは ロック (あるいは セマフォ ) です。ロックは２つのアトミックなアクションを提供します。すなわち、 獲得 と 解放 です。次は Scala におけるロックの実装です。 package scala.concurrent class Lock { var available = true def acquire = synchronized { while (!available) wait() available = false } def release = synchronized { available = true notify() } } 前ページ 17 章 目次 次ページ 名前 コメント